package P150;

/**
 * @author LiangMu
 * @version \$Id: P15.java, v 0.1, 2024年07月04日 17:27 LiangMu Exp $$
 */
public class P15 {

    public static int trap(int[] height) {
        // 先找最高的柱子
        int h = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[h] < height[i]) {
                h = i;
            }
        }
        // 以h为起点，向左遍历
        int sum = 0;
        if (h > 0) {
            int leftMax = 0;
            for (int i = 0; i < h; ++i) {
                if (height[i] > leftMax) {
                    leftMax = height[i];
                } else {
                    sum += leftMax - height[i];
                }
            }
        }
        // 以h为起点，向右遍历
        if (h < height.length) {
            int rightMax = 0;
            for (int i = height.length - 1; i > h; --i) {
                if (height[i] > rightMax) {
                    rightMax = height[i];
                } else {
                    sum += rightMax - height[i];
                }
            }
        }
        return sum;
    }


    public static void main(String[] args) {

    }

}
